/**
 * Created with IntelliJ IDEA.
 * Description: leetcode: 1799. N 次操作后的最大分数和
 * <a href="https://leetcode.cn/problems/maximize-score-after-n-operations/">...</a>
 * User: DELL
 * Date: 2023-10-11
 * Time: 10:04
 */
public class Solution {
    /**
     * 解题思路: (状态压缩+动态规划)
     * 因为题目中规定 n 的最大值是 7 ,也就是说数组的最大长度为 14,那么显而易见可以做
     * 一下状态压缩,即用一个整数 flag 来表示数组 nums 中未删除的数字状态,若 flag 的
     * 二进制串从右往左的第 i 位为 1,则说明原数组中的第 i 位未被删除，否则表示被删除。
     * 同时这样子做完状态压缩后,下一步的动态规划就慢慢显而易见了.
     * 状态定义: dp[i]: flag == i 时的最大分数和
     * 状态转移: 设 m = (i比特位中 1 的总位数)
     * 1) 当 m 为奇数时: 很明显这种情况直接舍弃即可,不符合题意,正常操作不可能出现的情况.
     * 2) 当 m 为偶数时: 遍历每一对未被删除的数字,找出最大值,假设未被删除的数字下标为 x 和 y
     * 即 dp[i] = Math.max(dp[i],dp[i^(1<<x)^(1<<y)]+[(2*n-m+2)/2]*gcd(nums[x],nums[y]))
     * (以上公式中的 ^ 表示异或)
     * 初始化: dp[i] = 0
     * 返回值: dp[1<<(2*n)-1]
     * 因为需要频繁求 gcd ,同时 n 的最大值为 7,因此可以做一下缓存
     *
     * @param nums
     * @return
     */
    public int maxScore(int[] nums) {
        int len = nums.length;
        int max = 1 << len;
        int[] dp = new int[max];
        // 缓存
        int[][] gcpBuffer = new int[len][len];
        for (int i = 0; i < len; i++) {
            for (int j = i + 1; j < len; j++) {
                gcpBuffer[i][j] = gcd(nums[i], nums[j]);
            }
        }
        for (int flag = 1; flag < max; flag++) {
            int m = Integer.bitCount(flag);
            // 跳过 m 为奇数的情况
            if ((m & 1) == 1) {
                continue;
            }
            // m为偶数,维护 dp数组
            for (int i = 0; i < len; i++) {
                if ((flag & (1 << i)) != 0) {
                    for (int j = i + 1; j < len; j++) {
                        if ((flag & (1 << j)) != 0) {
                            dp[flag] = Math.max(dp[flag], dp[flag ^ (1 << i) ^ (1 << j)] + ((len - m + 2) / 2) * gcpBuffer[i][j]);
                        }
                    }
                }
            }
        }
        return dp[max - 1];
    }

    private int gcd(int num1, int num2) {
        int temp = num1 % num2;
        while (temp != 0) {
            num1 = num2;
            num2 = temp;
            temp = num1 % num2;
        }
        return num2;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.gcd(15, 28));
    }
}
